package 栈和队列;

import java.util.*;

public class TopKFrequent {
    public int[] topKFrequent(int[] nums, int k) {
        int n = nums.length;
        TreeMap<Integer,Integer> treeMap = new TreeMap<Integer,Integer>();

        for(int i=0;i<n;i++){
            if(treeMap.containsKey(nums[i])){
                int temp = treeMap.get(nums[i]);
                treeMap.put(nums[i],temp+1);
            }else{
                treeMap.put(nums[i],1);
            }
        }
        List<Map.Entry<Integer, Integer>> list = new ArrayList<Map.Entry<Integer,Integer>>(treeMap.entrySet());
        Collections.sort(list,new Comparator<Map.Entry<Integer,Integer>>() {
            @Override
            public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
                return o2.getValue().compareTo(o1.getValue());
            }
        });
        int [] ans = new int[k];
        int m = 0;
        for (Map.Entry<Integer, Integer> e: list) {
            if(m==k) break;
            //System.out.println(e.getKey()+":"+e.getValue());
            ans[m++] = e.getKey();
        }
        return ans;
    }
    class Solution {
        public int[] topKFrequent(int[] nums, int k) {
            int[] result = new int[k];
            HashMap<Integer, Integer> map = new HashMap<>();
            for (int num : nums) {
                map.put(num, map.getOrDefault(num, 0) + 1);
            }

            Set<Map.Entry<Integer, Integer>> entries = map.entrySet();
            // 根据map的value值正序排，相当于一个小顶堆
            PriorityQueue<Map.Entry<Integer, Integer>> queue = new PriorityQueue<>((o1, o2) -> o1.getValue() - o2.getValue());
            for (Map.Entry<Integer, Integer> entry : entries) {
                queue.offer(entry);
                if (queue.size() > k) {
                    queue.poll();
                }
            }
            for (int i = k - 1; i >= 0; i--) {
                result[i] = queue.poll().getKey();
            }
            return result;
        }
    }
}

